/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

 //自己想到的使用键值对存储，但是效率太低
// class Solution {
// public:
//     ListNode* sortList(ListNode* head) {
//         if(!head||!head->next) return head;
//         multimap<int,ListNode*> hash;
//         ListNode* cur=head;
//         while(cur)
//         {
//             hash.insert({cur->val,cur});
//             cur=cur->next;
//         }
//         auto it=hash.begin();
//         head=it->second;
//         ListNode* prev=nullptr;
//         while(it!=hash.end())
//         {
//             if(prev)
//                 prev->next=it->second;
//             prev=it->second;
//             ++it;
//         }
//         prev->next=nullptr;
//         return head;
//     }
// };

//使用归并分治算法
class Solution {
public:
    //链表分段函数
    ListNode* middleNode(ListNode* head)
    {
        ListNode* pre=head;
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next)
        {   
            pre=slow;
            fast=fast->next->next;
            slow=slow->next;
        }
        pre->next=nullptr;//断开
        return slow;
    }

    ListNode* mergeNode(ListNode* list1,ListNode* list2)
    {
        ListNode dummy(0);
        ListNode* cur=&dummy;
        while(list1&&list2)
        {
            if(list1->val<list2->val)
            {
                cur->next=list1;
                list1=list1->next;
            }
            else
            {
                cur->next=list2;
                list2=list2->next;
            }
            cur=cur->next;
        }
        if(list1)
            cur->next=list1;
        else
            cur->next=list2;
        return dummy.next;
    }

    ListNode* sortList(ListNode* head) {
        if(!head||!head->next) return head;
        
        ListNode* midNode=middleNode(head);

        ListNode* node1=sortList(head);
        ListNode* node2=sortList(midNode);
        ListNode* ans=mergeNode(node1,node2);
        return ans;
        
    }
};<Paste>
